import com.dmall.tree.BST;
import com.dmall.tree.BinarySearchTree;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Random;

public class Main {

    public static void main(String[] args) {
        BST<Integer> bst = new BST<>();
        Random random = new Random();

        int n = 1000;
        for (int i = 0; i < n; i++) {
            bst.add(random.nextInt(10000));
        }

        ArrayList<Integer> nums = new ArrayList<>(n);
        /*while (!bst.isEmpty()) {
            nums.add(bst.removeMin());
        }
        for (int i = 1; i < nums.size(); i++) {
            if (nums.get(i) < nums.get(i - 1)) {
                throw new IllegalArgumentException("ERROR");
            }
        }
        System.out.println("removeMin test completed.");*/

        while (!bst.isEmpty()) {
            nums.add(bst.removeMax());
        }
        for (int i = 1; i < nums.size(); i++) {
            if (nums.get(i) > nums.get(i - 1)) {
                throw new IllegalArgumentException("ERROR");
            }
        }
        System.out.println("removeMax test completed.");
        System.out.println(nums.size());
        System.out.println(nums);
    }

    @Test
    public void test1() {
        int[] nums = {5, 3, 6, 8, 4, 2};
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int num : nums) {
            bst.add(num);
        }

        //////////////////////////
        //          5           //
        //         / \          //
        //        3   6         //
        //       / \   \        //
        //      2   4   8       //
        //////////////////////////

        // bst.preOrder();
        // System.out.println();
        // bst.preOrderNR();
        //System.out.println(bst);

        // bst.inOrder();

        // bst.postOrder();

        // bst.levelOrder();

//        System.out.println(bst.getMinNodeValue());
//        System.out.println(bst.getMaxNodeValue());

//        System.out.println(bst.minimum());
//        System.out.println(bst.maximum());

        System.out.println(bst.removeMin());
        System.out.println(bst.removeMax());
        System.out.println(bst);
    }

    @Test
    public void test2() {
        BST<Integer> bst = new BST<>();
        int[] nums = {5, 3, 6, 8, 4, 2};
        for (int num : nums) {
            bst.add(num);
        }

        /*bst.preOrder();
        System.out.println();
        bst.inOrder();
        System.out.println();
        bst.postOrder();
        System.out.println();
        bst.preOrderNR();
        System.out.println();*/
        //bst.levelOrder();
        //System.out.println();
        //System.out.println(bst);

        //bst.preOrder();
        //System.out.println();
        //bst.removeMin();
        //System.out.println();
        bst.preOrder();
        System.out.println();
        bst.removeMin();
        System.out.println();
        bst.preOrder();
    }

    @Test
    public void test3() {
        BST<Integer> bst = new BST<>();
        int[] nums = {5, 3, 6, 8, 4, 2};
        for (int num : nums) {
            bst.add(num);
        }
        //
        System.out.println("删除前：");
        bst.inOrder();
        /*System.out.println("删除元素5：");
        bst.remove(5);
        bst.preOrder();
        System.out.println("删除元素2：");
        bst.remove(2);
        bst.preOrder();
        System.out.println("删除元素3：");
        bst.remove(3);
        bst.preOrder();*/
    }
}
